#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n = stones.size(), sum = 0;
        for (int x : stones)
            sum += x;
        int aim = sum / 2;
        vector<vector<int>> dp(n + 1, vector<int>(sum + 1));
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j <= sum; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= stones[i - 1]) dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
            }
        }
        return abs(sum - 2 * dp[n][sum / 2]);
    }

    vector<int> knapsack(int v, int n, vector<vector<int> >& nums) {
        vector<vector<int>> dp(n + 1, vector<int>(v + 1));
        vector<vector<int>> f(n + 1, vector<int>(v + 1));
        for (int i = 1; i <= v; ++i)
            f[0][i] = -1;
        vector<int> ret;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j <= v; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1][0])dp[i][j] = max(dp[i][j], dp[i][j - nums[i - 1][0]] + nums[i - 1][1]);
                f[i][j] = f[i - 1][j];
                if (j >= nums[i - 1][0] && f[i][j - nums[i - 1][0]] != -1)f[i][j] = max(f[i][j], f[i][j - nums[i - 1][0]] + nums[i - 1][1]);
            }
        }
        f[n][v] = f[n][v] == -1 ? 0 : f[n][v];
        ret.push_back(dp[n][v]);
        ret.push_back(f[n][v]);
        return  ret;
    }

    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
        for (int i = 1; i <= amount; ++i)
            dp[0][i] = 0x3f3f3f3f;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j <= amount; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= coins[i - 1] && dp[i][j - coins[i - 1]] != -1)dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
            }
        }
        return dp[n][amount] >= 0x3f3f3f3f ? -1 : dp[n][amount];
    }

};

//const int N = 1010;
//
//int n, V;
//int w[N] = { 0 }, v[N] = { 0 };
//int f[N] = { 0 };
//int g[N] = { 0 };
//int main() {
//    cin >> n >> V;
//    for (int i = 1; i <= n; ++i)
//    {
//        cin >> v[i] >> w[i];
//    }
//    for (int i = 1; i <= V; ++i)
//        g[i] = -1;
//    for (int i = 1; i <= n; ++i)
//    {
//        for (int j = 0; j <= V; ++j)
//        {
//            if (j >= v[i])f[j] = max(f[j], f[j - v[i]] + w[i]);
//            if (j >= v[i] && g[j - v[i]] != -1)g[j] = max(g[j], g[j - v[i]] + w[i]);
//        }
//    }
//    cout << f[V] << endl << (g[V] == -1 ? 0 : g[V]);
//}

